/*  
 *  Board.cs - Representation of a chess board.
 *  Copyright(c) 2007 Adam W Adair
 *
 *  This file is part of Adam's Chess Engine (ACE).
 *
 *  ACE is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *   
 *  ACE is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with ACE; if not, write to the Free Software
 *  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 */
using System;
using System.Collections.Generic;
using System.Text;

namespace ACE.Board
{
    /// <summary>
    /// Chess board is the representation of an 8x8 chess board.  This class
    /// it keeps track of the pieces on the board and generates legal moves.
    /// It can also determine if a move is legal on the board.
    /// </summary>
    class ChessBoard
    {
        #region Board Constants
        // I know black and white are rather specific, but you get the point
        public const int WHITE = 0;
        public const int BLACK = 1;
        public const int EMPTY = -1;

        public const int NO_ENPASSANT = -1;

        public const int BOARD_COLUMNS = 8;
        public const int BOARD_ROWS = 8;
        public const int BOARD_SIZE = BOARD_COLUMNS * BOARD_ROWS;

        // Starting Board Positions -- notice 0 is on the black player'd side
        public const int A8 = 0;
        public const int B8 = 1;
        public const int C8 = 2;
        public const int D8 = 3;
        public const int E8 = 4;
        public const int F8 = 5;
        public const int G8 = 6;
        public const int H8 = 7;
        public const int A7 = 8;
        public const int B7 = 9;
        public const int C7 = 10;
        public const int D7 = 11;
        public const int E7 = 12;
        public const int F7 = 13;
        public const int G7 = 14;
        public const int H7 = 15;

        public const int A1 = 56;
        public const int B1 = 57;
        public const int C1 = 58;
        public const int D1 = 59;
        public const int E1 = 60;
        public const int F1 = 61;
        public const int G1 = 62;
        public const int H1 = 63;
        public const int A2 = 48;
        public const int B2 = 49;
        public const int C2 = 50;
        public const int D2 = 51;
        public const int E2 = 52;
        public const int F2 = 53;
        public const int G2 = 54;
        public const int H2 = 55;

        /// <summary>
        /// Chess programs typically used an array of 120 elements to represent the 
        /// 64 valid board squares, plus a 2-square borders around the 
        /// valid set of board square.  We modify this by creating a 120 element 
        /// array with valid array value as offsets into the board array, and invalid
        /// positions have the value -1.
        /// </summary>
        public static readonly int[] ValidationArray = 
        {
	        -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
	        -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
	        -1,  0,  1,  2,  3,  4,  5,  6,  7, -1,
	        -1,  8,  9, 10, 11, 12, 13, 14, 15, -1,
	        -1, 16, 17, 18, 19, 20, 21, 22, 23, -1,
	        -1, 24, 25, 26, 27, 28, 29, 30, 31, -1,
	        -1, 32, 33, 34, 35, 36, 37, 38, 39, -1,
	        -1, 40, 41, 42, 43, 44, 45, 46, 47, -1,
	        -1, 48, 49, 50, 51, 52, 53, 54, 55, -1,
	        -1, 56, 57, 58, 59, 60, 61, 62, 63, -1,
	        -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
	        -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
        };

        /// <summary>
        /// A jump table into the ValidationArray from the board array.  For instance
        /// board square is a8 is at offset 0 in the board array but offest 21 in the 
        /// validation array.
        /// </summary>
        public static readonly int[] ValidationJump = 
        {
	        21, 22, 23, 24, 25, 26, 27, 28,
	        31, 32, 33, 34, 35, 36, 37, 38,
	        41, 42, 43, 44, 45, 46, 47, 48,
	        51, 52, 53, 54, 55, 56, 57, 58,
	        61, 62, 63, 64, 65, 66, 67, 68,
	        71, 72, 73, 74, 75, 76, 77, 78,
	        81, 82, 83, 84, 85, 86, 87, 88,
	        91, 92, 93, 94, 95, 96, 97, 98
        };

        public const string BOARD_DIVIDER = "\n  ---+---+---+---+---+---+---+---";
        #endregion

        #region Board Attributes
        /// <summary>
        /// Side that needs to move, 0=WHITE, 1=BLACK
        /// </summary>
        public int SideToMove;               // side to move
        /// <summary>
        /// Side not moving, 0=WHITE, 1=BLACK
        /// </summary>
        public int OtherSide
        {
            // simply the exclusive or of the SideToMove attribute.
            get { return SideToMove ^ 1; }
        }

        /// <summary>
        /// enpassant square
        /// </summary>
        public int EnpassantSqr;          
        /// <summary>
        /// number of moves since last capture
        /// </summary>
        public int NoCaptureMoves;          
        /// <summary>
        /// Number of half movesThis is relative to the  starting posistion.  
        /// It is possible for a fen position to start mid game at ply 0.
        /// </summary>
        public int Ply;              
        /// <summary>
        /// Hash of the current board position
        /// </summary>
        public int hash;                      
        /// <summary>
        /// Ply since the start of the game.
        /// </summary>
        public int GamePly;
        /// <summary>
        /// Game move number.  Increments when black moves.
        /// </summary>
        public int GameMove;
        /// <summary>
        /// true if white can castle king side
        /// </summary>
        public bool WhiteCanCastleKingSide;
        /// <summary>
        /// true if black can castle kingside
        /// </summary>
        public bool BlackCanCastleKingSide;
        /// <summary>
        /// true if white can castle queen side
        /// </summary>
        public bool WhiteCanCastleQueenside;
        /// <summary>
        /// true if black can castle queen side
        /// </summary>
        public bool BlackCanCastleQueenside;

        #endregion


        BoardSquare[] m_squares;            // The 8x8 board
        BoardSquare[] m_backup;             // backup of the board used during fen parsing.
        List<Move> m_moves;                 // The list of generated potential moves
        Stack<BoardStatus> m_history;       // History of moves and associated board statuses.

        public ChessBoard()
        {
            m_squares = init_board();
            m_moves = new List<Move>();
            m_history = new Stack<BoardStatus>();
        }

        /// <summary>
        /// This constructor initilizes the board give a FEN string.  This will throw 
        /// an exception if the FEN string is not a valid position.
        /// </summary>
        /// <param name="FEN"></param>
        public ChessBoard(string FEN)
        {
            m_moves = new List<Move>();
            m_history = new Stack<BoardStatus>();
            FEN_Position(FEN);
        }

        /// <summary>
        /// The squares of the board.
        /// </summary>
        public BoardSquare[] Squares
        {
            get { return m_squares; }
        }

        public List<Move> MoveHistory
        {
            get
            {
                List<Move> ml = new List<Move>();
                BoardStatus[] statuses = m_history.ToArray();
                int ssize = statuses.Length;
                for (int i = ssize - 1; i >= 0; --i)
                {
                    ml.Add(statuses[i].MoveMade);
                }
                return ml;
            }
        }

        public Stack<BoardStatus> PlayHistory
        {
            get
            {
                return m_history;
            }
        }

        /// <summary>
        /// Returns the list of potential moves.
        /// </summary>
        public List<Move> PotentialMoves
        {
            get { return m_moves; }
        }

        private BoardSquare[] init_board()
        {
            BoardSquare[] board = new BoardSquare[BOARD_SIZE];
            BoardSquare.SquareColor color = BoardSquare.SquareColor.Dark;
            for (int row = 0; row < BOARD_ROWS; ++row)
            {
                color = BoardSquare.GetOppositeColor(color);
                for (int col = 0; col < BOARD_COLUMNS; ++col)
                {
                    int pos = (row * 8) + col;
                    board[pos] = new BoardSquare(color);
                    color = BoardSquare.GetOppositeColor(color);
                }
            }
            return board;
        }

        /// <summary>
        /// Generates a list of all potential moves.  This list can found in the
        /// attribute MoveList.
        /// </summary>
        public void GeneratePotentialMoves()
        {
            Move tmpMove = null;
            Piece.PlayerColor side = (SideToMove == WHITE) ? Piece.PlayerColor.White : Piece.PlayerColor.Black;
            m_moves.Clear();
            for (int i = 0; i < BOARD_SIZE; ++i)
            {
                if (m_squares[i].Piece != null &&
                    m_squares[i].Piece.Color == side)
                {
                    List<Move> ml = m_squares[i].Piece.GeneratePotentialMoves(this, i);
                    m_moves.AddRange(ml);
                }
            }

            // add castling moves if they are still in play
            if (side == Piece.PlayerColor.White)
            {
                if (WhiteCanCastleKingSide)
                {
                    tmpMove = new Move(E1, G1, m_squares[E1].Piece);
                    tmpMove.IsCastle = true;
                    m_moves.Add(tmpMove);
                }
                if (WhiteCanCastleQueenside)
                {
                    tmpMove = new Move(E1, C1, m_squares[E1].Piece);
                    tmpMove.IsCastle = true;
                    m_moves.Add(tmpMove);
                }
            }
            else
            {
                if (BlackCanCastleKingSide)
                {
                    tmpMove = new Move(E8, G8, m_squares[E1].Piece);
                    tmpMove.IsCastle = true;
                    m_moves.Add(tmpMove);
                }
                if (BlackCanCastleQueenside)
                {
                    tmpMove = new Move(E8, C8, m_squares[E1].Piece);
                    tmpMove.IsCastle = true;
                    m_moves.Add(tmpMove);
                }
            }
            SortMoveList();
        }

        /// <summary>
        /// Sort the generated move list.
        /// </summary>
        public void SortMoveList()
        {
            if(m_moves==null)return;  // null lists are already sorted.
            Comparison<Move> comp = Move.CompareMovesByScore;
            m_moves.Sort(comp);
        }




        /// <summary>
        /// Clear the pieces from the board.
        /// </summary>
        public void Clear()
        {
            for (int i = 0; i < BOARD_SIZE; ++i)
            {
                m_squares[i].CleareSquare();
            }
        }

        /// <summary>
        /// Clears the board and sets up the starting position for all pieces.
        /// </summary>
        public void SetupInitialPosition()
        {
            Clear();
            //setup dark pieces
            m_squares[A8].Piece = Rook.BlackRook;
            m_squares[B8].Piece = Knight.BlackKnight;
            m_squares[C8].Piece = Bishop.BlackBishop;
            m_squares[D8].Piece = Queen.BlackQueen;
            m_squares[E8].Piece = King.BlackKing;
            m_squares[F8].Piece = Bishop.BlackBishop;
            m_squares[G8].Piece = Knight.BlackKnight;
            m_squares[H8].Piece = Rook.BlackRook;
            for (int sqr = A7; sqr <= H7; ++sqr)
            {
                m_squares[sqr].Piece = Pawn.BlackPawn;
            }

            //setup white pieces
            m_squares[A1].Piece = Rook.WhiteRook;
            m_squares[B1].Piece = Knight.WhiteKnight;
            m_squares[C1].Piece = Bishop.WhiteBishop;
            m_squares[D1].Piece = Queen.WhiteQueen;
            m_squares[E1].Piece = King.WhiteKing;
            m_squares[F1].Piece = Bishop.WhiteBishop;
            m_squares[G1].Piece = Knight.WhiteKnight;
            m_squares[H1].Piece = Rook.WhiteRook;

            for (int sqr = A2; sqr <= H2; ++sqr)
            {
               m_squares[sqr].Piece = Pawn.WhitePawn;
            }
            WhiteCanCastleKingSide =
            WhiteCanCastleQueenside =
            BlackCanCastleKingSide =
            BlackCanCastleQueenside = true;
            
            SideToMove = WHITE;
            //OtherSide = BLACK;
            EnpassantSqr = NO_ENPASSANT;
            NoCaptureMoves = 0;
            Ply = 0;
            hash = 0;
            GamePly = 0;
            GeneratePotentialMoves();
        }

        /// <summary>
        /// Setup board from FEN string.  FEN (Forsyth-Edwards) notation is described
        /// in section 16.1 of this document: http://www.chessclub.com/help/PGN-spec.
        /// This needs to be rock solid, because UCI utilizes FEN extensively.
        /// </summary>
        /// <param name="fen"></param>
        public void FEN_Position(string fen)
        {
            string[] fields = fen.Split(" ".ToCharArray());
            if (fields.Length != 6) throw new ACEException("Invalid FEN record");
            // 1) place the pieces.
            fen_place_pieces(fields[0]);
            m_squares = m_backup;

            // 2) Set the side to move
            string szSide = fields[1].ToLower();
            if (szSide == "b")
                SideToMove = BLACK;
            else if (szSide == "w")
                SideToMove = WHITE;
            else
                throw new ACEException("Invalid FEN Record: side to move bust be 'b' or 'w'");

            // 3) set castle abilities
            fen_set_castles(fields[2]);

            // 4) set enpassant target
            if (fields[3].Trim() != "-")
                EnpassantSqr = SquareNumber(fields[3].Trim());
            else
                EnpassantSqr = NO_ENPASSANT;
            
            // 5) set ply number
            Ply = 0;
            try
            {
                GamePly = int.Parse(fields[4]);
            }
            catch
            {
                throw new ACEException("Invalid Fen Record: " + fields[4] + " is not a valid ply number");
            }

            // 6) set the game move number
            try
            {
                GameMove = int.Parse(fields[5]);
            }
            catch
            {
                throw new ACEException("Invalid Fen Record: " + fields[5] + " is not a valid game move number");
            }
            GeneratePotentialMoves();
        }

        private void fen_place_pieces(string fen_pos)
        {
            m_backup = init_board();
            string[] ranks = fen_pos.Split("/".ToCharArray());
            if (ranks.Length != 8) throw new ACEException("Invalid FEN Record:  8 ranks required in piece placement data.");
            int count = 0;
            for (int i = 0; i < ranks.Length; ++i)
            {
                char[] files = ranks[i].ToCharArray();
                for (int j = 0; j < files.Length; ++j)
                {
                    if (char.IsDigit(files[j]))
                    {
                        count += Util.CharToInt(files[j]);
                    }
                    else
                    {
                        m_backup[count].Piece = GetPieceFromChar(files[j]);
                        ++count;
                    }
                }
            }
        }

        private void fen_set_castles(String fen_castle)
        {
            // initialize all castle attributes to false
            WhiteCanCastleKingSide =
            WhiteCanCastleQueenside =
            BlackCanCastleKingSide =
            BlackCanCastleQueenside = false;
            char[] cc = fen_castle.ToCharArray();
            for (int i = 0; i < cc.Length; ++i)
            {
                switch (cc[i])
                {
                    case 'K':
                        WhiteCanCastleKingSide = true;
                        break;
                    case 'Q':
                        WhiteCanCastleQueenside = true;
                        break;
                    case 'k':
                        BlackCanCastleKingSide = true;
                        break;
                    case 'q':
                        BlackCanCastleQueenside = true;
                        break;
                }
            }
        }

        public static Piece GetPieceFromChar(char p)
        {
            switch (p)
            {
                case 'p':
                    return Pawn.BlackPawn;
                case 'r':
                    return Rook.BlackRook;
                case 'n':
                    return Knight.BlackKnight;
                case 'b':
                    return Bishop.BlackBishop;
                case 'q':
                    return Queen.BlackQueen;
                case 'k':
                    return King.BlackKing;
                case 'P':
                    return Pawn.WhitePawn;
                case 'R':
                    return Rook.WhiteRook;
                case 'N':
                    return Knight.WhiteKnight;
                case 'B':
                    return Bishop.WhiteBishop;
                case 'Q':
                    return Queen.WhiteQueen;
                case 'K':
                    return King.WhiteKing;
            }
            return null;
        }

        /// <summary>
        /// Gets the board row (rank) of this square.
        /// </summary>
        /// <param name="sqr">square number</param>
        /// <returns></returns>
        public static int Row(int sqr)
        {
            return sqr / BOARD_ROWS;
        }

        /// <summary>
        /// Gets the board column (file) for the square
        /// </summary>
        /// <param name="sqr"></param>
        /// <returns></returns>
        public static int Column(int sqr)
        {
            return sqr % BOARD_COLUMNS;
        }

        /// <summary>
        /// returns the offset into the baord array for the position.
        /// </summary>
        /// <param name="row">rank</param>
        /// <param name="col">file</param>
        /// <returns>offset</returns>
        public static int SquareNumber(int row, int col)
        {
            return (row * BOARD_ROWS) + col;
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="pos"></param>
        /// <param name="color"></param>
        /// <returns></returns>
        public bool ContainsEnemy(int pos, Piece.PlayerColor color)
        {
            if (Squares[pos].Piece != null)
            {
                return (color != Squares[pos].Piece.Color);
            }
            return false;
        }

        /// <summary>
        /// checks if a square is attacked by a side.
        /// </summary>
        /// <param name="square">The square to check</param>
        /// <param name="side">The attacking side</param>
        /// <returns>true if it is attacking.</returns>
        public bool IsAttacked(int square, int side)
        {
            for (int i = 0; i < BOARD_SIZE; ++i)
            {
                if (m_squares[i].Owner == side)
                {
                    if (m_squares[i].Piece.IsAttackingSqaure(this, i, square)) return true;
                }
            }

            return false;
        }

        /// <summary>
        /// checks if a side is in check
        /// </summary>
        /// <param name="side">side to check</param>
        /// <returns>true if the side is in check</returns>
        public bool InCheck(int side)
        {
            for (int i = 0; i < BOARD_SIZE; ++i)
            {
                if (m_squares[i].Owner == side && m_squares[i].Piece is King)
                    return IsAttacked(i, (side ^ 1));
            }
            return false;  // Since there is always a king on the board we should never reach this line.
        }

        /// <summary>
        /// Returns whether the side to move is in check.
        /// </summary>
        /// <returns>true if the side to move is in check.</returns>
        public bool InCheck()
        {
            return InCheck(SideToMove);
        }

        /// <summary>
        /// Checks if there is a legal move exists on the board.
        /// </summary>
        /// <returns></returns>
        public bool LegalMoveExists()
        {
            for(int i = 0; i < PotentialMoves.Count; ++i)
            {
                if(MakeMove(PotentialMoves[i]))
                {
                    TakeBackMove();
                    return true;
                }
            }
            return false;
        }

        /// <summary>
        /// Checks if move is a legal move on this board.
        /// </summary>
        /// <param name="move"></param>
        /// <returns></returns>
        public bool IsMoveLegal(Move move)
        {
            if (MakeMove(move))
            {
                TakeBackMove();
                return true;
            }
            return false;
        }

        /// <summary>
        /// Returns true if side to move is in check.
        /// </summary>
        /// <returns></returns>
        public bool IsMovingSideChecked()
        {
            return InCheck(SideToMove);
        }

        public bool MakeMove(Move move)
        {
            if (move.IsCastle)
            {
                int from = 0, to = 0;
                if (InCheck(SideToMove))
                    return false;
                switch (move.To)
                {
                    case G1:
                        if (m_squares[F1].Owner != EMPTY ||
                            m_squares[G1].Owner != EMPTY ||
                            IsAttacked(F1, OtherSide) ||
                            IsAttacked(G1, OtherSide))
                            return false;
                        from = H1;
                        to = F1;
                        break;
                    case C1:
                        if (m_squares[B1].Owner != EMPTY ||
                            m_squares[C1].Owner != EMPTY ||
                            m_squares[D1].Owner != EMPTY ||
                            IsAttacked(C1, OtherSide) ||
                            IsAttacked(D1, OtherSide))
                            return false;
                        from = A1;
                        to = D1;
                        break;
                    case G8:
                        if (m_squares[F8].Owner != EMPTY ||
                            m_squares[G8].Owner != EMPTY ||
                            IsAttacked(F8, OtherSide) ||
                            IsAttacked(G8, OtherSide))
                            return false;
                        from = H8;
                        to = F8;
                        break;
                    case C8:
                        if (m_squares[B8].Owner != EMPTY ||
                            m_squares[C8].Owner != EMPTY ||
                            m_squares[D8].Owner != EMPTY ||
                            IsAttacked(C8, OtherSide) ||
                            IsAttacked(D8, OtherSide))
                            return false;
                        from = A8;
                        to = D8;
                        break;
                }
                move_piece(from, to);
            }
            // Push board data and move onto history stack.  We do this incase 
            // we need to take the move back
            m_history.Push(new BoardStatus(this, move));


            // Move the piece
            if (move.IsPromotion)
                move_piece_and_promote(move.From, move.To, move.PromotionPiece);
            else
                move_piece(move.From, move.To);
            // if it was enpassant, remove the pawn
            if (move.IsEnpassantCapture)
            {
                if (SideToMove == WHITE)
                {
                    m_squares[move.To + 8].Piece = null;  // bye-bye black pawn
                }
                else
                {
                    m_squares[move.To - 8].Piece = null;  // bye-bye white pawn
                }
            }

            // Update castle flags.
            if (WhiteCanCastleQueenside || WhiteCanCastleKingSide || BlackCanCastleKingSide || BlackCanCastleQueenside)
                update_castle_flags();

            if (move.IsPushingPawn2)
            {
                if (SideToMove == WHITE)
                    EnpassantSqr = move.To + 8;
                else
                    EnpassantSqr = move.To - 8;
            }
            else
                EnpassantSqr = NO_ENPASSANT;

            if (move.IsCapture || move.IsPawnMove)
                NoCaptureMoves = 0;
            else
                ++NoCaptureMoves;

            if (SideToMove == BLACK) ++GameMove;

            SideToMove ^= 1;
            //OtherSide ^= 1;
            ++Ply;
            ++GamePly;

            if (InCheck(OtherSide))
            {
                // The move put own king in check.  This is illegal, and must be taken back.
                TakeBackMove();
                return false;
            }
            return true;
        }

        public void TakeBackMove()
        {
            BoardStatus bs = m_history.Pop();
            Move move = bs.MoveMade;
            SideToMove = bs.SideToMove;
            //OtherSide = bs.OtherSide;
            EnpassantSqr = bs.EnpassantSqr;
            NoCaptureMoves = bs.NoCaptureMoves;
            Ply = bs.Ply;
            GamePly = bs.GamePly;
            GameMove = bs.GameMove;
            WhiteCanCastleKingSide = bs.WhiteCanCastleKingSide;
            BlackCanCastleKingSide = bs.BlackCanCastleKingSide;
            WhiteCanCastleQueenside = bs.WhiteCanCastleQueenside;
            BlackCanCastleQueenside = bs.BlackCanCastleQueenside;  
            //if castle then uncastle
            if (move.IsCastle)
            {
                if (move.To == G1)
                {
                    m_squares[E1].Piece = King.WhiteKing;
                    m_squares[F1].Piece = null;
                    m_squares[G1].Piece = null;
                    m_squares[H1].Piece = Rook.WhiteRook;
                }
                else if (move.To == C1)
                {
                    m_squares[E1].Piece = King.WhiteKing;
                    m_squares[C1].Piece = null;
                    m_squares[D1].Piece = null;
                    m_squares[A1].Piece = Rook.WhiteRook;
                }
                else if (move.To == G8)
                {
                    m_squares[E8].Piece = King.BlackKing;
                    m_squares[F8].Piece = null;
                    m_squares[G8].Piece = null;
                    m_squares[H8].Piece = Rook.BlackRook;
                }
                else if (move.To == C8)
                {
                    m_squares[E8].Piece = King.BlackKing;
                    m_squares[C8].Piece = null;
                    m_squares[D8].Piece = null;
                    m_squares[A8].Piece = Rook.BlackRook;
                }
            }
            else
            {
                m_squares[move.From].Piece = move.MovingPiece;
                m_squares[move.To].Piece = move.CapturePiece;
                if (move.IsEnpassantCapture)
                {
                    if (SideToMove == WHITE)
                    {
                        m_squares[move.To + 8].Piece = Pawn.BlackPawn;
                    }
                    else
                    {
                        m_squares[move.To - 8].Piece = Pawn.WhitePawn;
                    }
                }
            }
        }

        private void move_piece(int from, int to)
        {
            m_squares[to].Piece = m_squares[from].Piece;
            m_squares[from].Piece = null;
        }

        private void move_piece_and_promote(int from, int to, Piece promotion)
        {
            m_squares[from].Piece = null;
            m_squares[to].Piece = promotion;
        }

        private void update_castle_flags()
        {
            bool wkinghome = (m_squares[E1].Piece==King.WhiteKing);
            bool wkrookhome = (m_squares[H1].Piece==Rook.WhiteRook);
            bool wqrookhome = (m_squares[A1].Piece==Rook.WhiteRook);
            if (WhiteCanCastleKingSide)
            {
                WhiteCanCastleKingSide = (wkinghome && wkrookhome);
            }
            if (WhiteCanCastleQueenside)
            {
                WhiteCanCastleQueenside = (wkinghome && wqrookhome);
            }

            bool bkinghome = (m_squares[E8].Piece == King.BlackKing);
            bool bkrookhome = (m_squares[H8].Piece == Rook.BlackRook);
            bool bqrookhome = (m_squares[A8].Piece == Rook.BlackRook);
            if (BlackCanCastleKingSide)
            {
                BlackCanCastleKingSide = (bkinghome && bkrookhome);
            }
            if (BlackCanCastleQueenside)
            {
                BlackCanCastleQueenside = (bkinghome && bqrookhome);
            }
        }

        public void undo()
        {
            if (m_history.Count > 0)
            {
                TakeBackMove();
                GeneratePotentialMoves();
            }
        }

        /// <summary>
        /// Returns the the offset into the board array for the give baord position.
        /// e.g. "a8" = 0, "h1" = 63
        /// </summary>
        /// <param name="sqr">board position</param>
        /// <returns>offset into the board array</returns>
        public static int SquareNumber(string sqr)
        {
            try
            {
                char[] ca = sqr.ToCharArray();
                if (ca[0] < 'a' || ca[0] > 'h') throw new ACEException("Invalid file letter" + ca[0]);
                int col = 8 - ((int)('h' - ca[0])) - 1;
                int row = 0;
                if (char.IsDigit(ca[1])){
                    row = (int)char.GetNumericValue(ca[1]);
                    row = 8 - row;
                }
                else
                    throw new ACEException("Invalid rank: " + ca[1]);
                return SquareNumber(row, col);
                
            }
            catch (ACEException aceex)
            {
                throw aceex;
            }
            catch
            {
                throw new ACEException("Invalid board position: " + sqr);
            }
        }

        /// <summary>
        /// returns the algebraic board position coordinate for the give offset.
        /// </summary>
        /// <param name="offset">board array offset</param>
        /// <returns>the board coordinate</returns>
        public static string GetCoordinate(int offset)
        {
            if ((offset < 0) || offset >= BOARD_SIZE) throw new ACEException("Invalid board offset.");

            StringBuilder sb = new StringBuilder(2);
            int row = offset / BOARD_ROWS;
            char rowdigit = (char)('8' - row);
            int col = (offset % BOARD_COLUMNS);
            char colchar = (char)('a' + col);
            sb.Append(colchar);
            sb.Append(rowdigit);
            return sb.ToString();
        }

        /// <summary>
        /// override the ToString method to provide a string display of the board.
        /// 
        /// TODOD:  put the side to move.
        /// </summary>
        /// <returns>Text representation of the board.</returns>
        public override string ToString()
        {
            StringBuilder display = new StringBuilder();

            for (int i = 0; i < BOARD_SIZE; ++i)
            {
                int col = Column(i);
                if (col == 0)
                {
                    if (i > 0)
                    {
                        display.Append(BOARD_DIVIDER);
                    }
                    display.Append("\n");
                    display.Append(((int)(8-Row(i))).ToString());
                    display.Append(" ");
                } 
                else 
                {
                    display.Append("|");
                }

                if (m_squares[i].Piece == null)
                {
                    display.Append("   ");
                }
                else
                {
                    display.Append(" " + m_squares[i].Piece.DisplayChar + " ");
                }
            }
            display.Append("\n\n   a   b   c   d   e   f   g   h\n");
            display.Append("Move: " + (GameMove + 1));
            display.Append("  Ply: " + (GamePly + 1) + "  ");
            string pcolor = (SideToMove==WHITE)?"White to move  ":"Black to move  ";
            display.Append(pcolor);
            if (WhiteCanCastleKingSide) display.Append("K");
            if (WhiteCanCastleQueenside) display.Append("Q");
            if (BlackCanCastleKingSide) display.Append("k");
            if (BlackCanCastleQueenside) display.Append("q");

            display.Append("\n");
            if (EnpassantSqr > NO_ENPASSANT)
            {
                display.Append("Enpassant square = ");
                display.Append(GetCoordinate(EnpassantSqr));
                display.Append("\n");
            }
            return display.ToString();
        }
    }

    /// <summary>
    /// Represents a single square on the playing board.  We even keep track of the 
    /// color of the square, even though it isn't necessary to the playing of the
    /// chess game it could be used when displaying the board visually.
    /// </summary>
    class BoardSquare
    {
        public enum SquareColor { Light, Dark };
        private SquareColor m_color;
        private Piece m_piece;

        public BoardSquare(SquareColor c)
        {
            m_color = c;
            m_piece = null;
        }

        /// <summary>
        /// Color of the square
        /// </summary>
        public SquareColor Color
        {
            get
            {
                return m_color;
            }
        }

        /// <summary>
        /// Piece on the square.
        /// </summary>
        public Piece Piece
        {
            get
            {
                return m_piece;
            }
            set
            {
                m_piece = value;
            }
        }

        /// <summary>
        /// This is a convenience function to determine the side that occupies a square.  The code
        /// was getting bloated making the check to see if the piece was not null and then which
        /// side was the owner.  I regret making the piece color an enum type, because it really
        /// explodes the size of the code.
        /// 0 = WHITE
        /// 1 = BLACK
        /// -1 = EMPTY
        /// </summary>
        public int Owner
        {
            get
            {
                if (this.Piece != null)
                {
                    if (this.Piece.Color == Piece.PlayerColor.White) return 0;
                    else return 1;
                }
                return -1;
            }
        }

        /// <summary>
        /// removes any piece that is on the square.
        /// </summary>
        public void CleareSquare()
        {
            this.Piece = null;
        }

        public static SquareColor GetOppositeColor(SquareColor c)
        {
            return (c == SquareColor.Light) ? SquareColor.Dark : SquareColor.Light;
        }
    }
}
